package com.gxc.array;

import java.util.ArrayList;
import java.util.List;

/**
 * 54. 螺旋矩阵
 * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素
 */
public class SpiralOrder {

    public static void main(String[] args) {
        List<Integer> list = handle(new int[][]{
                {1,2,3},{4,5,6},{7,8,9}
        });
        print(list);
        list = handle(new int[][]{
                {1,2,3, 4},{5,6,7,8},{9,10,11,12}
        });
        print(list);
        list = handle(new int[][]{
                {6,9,7}
        });
        print(list);
    }

    /**
     * 递归
     * @param matrix
     * @return
     */
    public static List<Integer> handle(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        recursion(matrix, 0 , matrix.length-1, 0, matrix[0].length-1, list);
        return list;
    }

    public static void recursion(int[][] matrix, int rowS, int rowE, int colS, int colE, List<Integer> list) {
        if (rowS>rowE || colS>colE) return;

        for (int i = colS; i <= colE; i++) {
            list.add(matrix[rowS][i]);
        }
        for (int i = rowS+1; i <= rowE; i++) {
            list.add(matrix[i][colE]);
        }
        for (int i = colE-1; i >= colS && rowE!=rowS; i--) {
            list.add(matrix[rowE][i]);
        }
        for (int i = rowE-1; i > rowS  && colS!=colE; i--) {
            list.add(matrix[i][colS]);
        }

        recursion(matrix, rowS+1, rowE-1, colS+1, colE-1, list);
    }

    /**
     * 非递归
     * @param matrix
     * @return
     */
    public static List<Integer> handle2(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        int rowS = 0, colS = 0;
        int rowE = matrix.length-1, colE = matrix[0].length-1;
        while (rowS<=rowE && colS<=colE) {
            for (int i = colS; i <= colE; i++) {
                list.add(matrix[rowS][i]);
            }
            for (int i = rowS+1; i <= rowE; i++) {
                list.add(matrix[i][colE]);
            }
            for (int i = colE-1; i >= colS && rowE!=rowS; i--) {
                list.add(matrix[rowE][i]);
            }
            for (int i = rowE-1; i > rowS  && colS!=colE; i--) {
                list.add(matrix[i][colS]);
            }
            rowS++;
            rowE--;
            colS++;
            colE--;
        }
        return list;
    }

    private static void print(List<Integer> list) {
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.println("");
    }

    class Solution {
        public List<Integer> spiralOrder(int[][] matrix) {
            List<Integer> order = new ArrayList<Integer>();
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return order;
            }
            int rows = matrix.length, columns = matrix[0].length;
            boolean[][] visited = new boolean[rows][columns];
            int total = rows * columns;
            int row = 0, column = 0;
            //四个转向
            int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
            int directionIndex = 0;
            for (int i = 0; i < total; i++) {
                order.add(matrix[row][column]);
                visited[row][column] = true;
                int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
                if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
                    directionIndex = (directionIndex + 1) % 4;
                }
                row += directions[directionIndex][0];
                column += directions[directionIndex][1];
            }
            return order;
        }
    }

}
